//
// 快速排序： 一组无序数字，将其按顺序排列
// 在这组数中任选一数，以这个数为界，将数组分为左右两边，将
// Created by Mzoro on 2022/3/22.
//
#include <stdio.h>

#define ARRAY_SIZE(X)  sizeof(X)/sizeof(X[0])


/**
 * 将数组 x 位置的数和 y 位置的数交换
 * @param arr 数组
 * @param x index
 * @param y index
 */
void swap(int arr[], int x, int y);

/**
 * 递归排序，这个方法不会一次将arr排序完成 ，每次调用只排 从 start 到end 的数
 *
 * 递归不是最好的排序方法，对于一个很长的数组，可能会出现调用栈过深，出现异常
 * @param arr 要排序的数组
 * @param start  要排从哪到哪的内个数， 开始位置
 * @param end   结束
 */
void sort(int arr[], int start, int end);

int main() {

    int arr[12] = {8, 3, 6, 5, 66, 2, 99, 5, 25, 66, 44, 1};
    sort(arr, 0, ARRAY_SIZE(arr) - 1);
    printf("");
}

void sort(int arr[], const int start, const int end) {

    if (start >= end) {
        return;
    }

    int pr = arr[start];
    int i = start + 1;
    int j = end;

    // 假设pr 是最大的数
    int prIsMax = 1;
    // 假设pr 是最小的数
    int psIsMin = 1;
    for (; i < j; ++i) {
        if (arr[i] > pr) {
            prIsMax = 0;
            // 从左向右找，只要大于 pr 就向右换，换小于等于pr那个,从右往左找
            for (; i < j; j--) {
                if (arr[j] <= pr) {
                    // 说明不是最小的
                    psIsMin = 0;
                    swap(arr, i, j);
                    break;
                }
            }
        }
    }


    if (prIsMax) {
        // 当 pr 是这组数中的最大值，这里要补充比较最近一个值，因为上面的循环中没有比较最后一个值
        int k ;
        for (k = end; k > start; --k) {
            if (arr[k] < pr) {
                swap(arr, k, start);
                break;
            }
        }
        sort(arr, start, k);
    } else {
        i--;
        if (psIsMin) {
            sort(arr, i, end);
        } else {
            swap(arr, start, (i - 1));
            sort(arr, start, (i - 1));
            sort(arr, i, end);
        }
    }
}

void swap(int arr[], int x, int y) {
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}
